Print data that is transmitted between various processes within a printing system is often encoded in a Run length (RL) format to reduce the amount of bandwidth utilized to transmit the print data and/or to store the print data. Before printing the RL encoded print data, the print data is decoded and screened using a “halftone” process. Halftoning is a reprographic technique that simulates a continuous tone image with dots, where the dots may vary either in size and/or in spacing. Where continuous tone images may contain an infinite range of colors or grays, a typical halftone image generated by a printing system is a binary image comprising a limited set of colors such as black, Cyan, Magenta, Yellow, and Key black (CMYK), or Red Green Blue (RGB). This type of binary reproduction relies on the optical illusion that tiny dots can generate smooth image tones when viewed by the human eye, thus appearing to be a continuous tone image to the viewer.
Halftoning uses a high frequency/low frequency dichotomy to generate a continuous tone illusion from a halftone image. In halftoning, the low frequency component is a local area of the output image designated as a halftone cell. Each halftone cell relates to a corresponding area (size and location) of the continuous tone input image. Within each halftone cell, the high frequency component is a variable-sized halftone dot composed of ink or toner. The ratio of the inked area to the non-inked area within the halftone cell represents the luminosity of the corresponding area on the continuous tone input image. From a distance, the human eye averages both the high frequency component corresponding to the ink ratio within the halftone cell and the low frequency component corresponding to the size of the halftone cell.
In digital halftoning, a raster image processor generates a raster image, or bitmap, which comprises a 2-dimensional array of pixels (also known as pels). In order to simulate the halftone cell, the digital halftone cell contains groups of monochrome (e.g., black) or limited color pixels (e.g., CMYK) within the same sized halftone area. The location and sizes of the monochrome or limited color pixels within the digital halftone cell represent the high frequency/low frequency dichotomy of the halftone method described above.
In a typical digital printing system, Page Description Language (PDL) data, such as PostScript data, PDF (Portable Document Format) data, Intelligent Printer Data Stream (IPDS) data, Advanced Function Presentation (AFP) data, Mixed Object: Document Content Architecture (MODCA) data, or other types of PDL data is rasterized and converted into bitmap data. Monochrome data may be represented by a single 2-dimensional array of pixels, while color data may be represented by multiple 2-dimensional arrays of pixels, one for each color. The bitmap data may then be encoded to reduce the size of the data when transmitting the bitmap data through various post rasterizing processes within the printing system.
One type of RL encoding used by printing systems to reduce the size of data is PackBits. Apple Computer Inc. introduced PackBits with the release of the Macintosh® computer. A PackBits datastream includes packets with a one-byte header followed by one or more bytes of data. The header is a signed byte and defines the following data bytes as either literal data or repeat data. Literal data in PackBits represents data “as is”. Repeat data in PackBits represents runs of data, which remains the same. The header in PackBits also defines the number of bytes of encoded literal data or encoded repeat data. In other words, the header encodes both the type of data (literal or repeat) and the amount of encoded data (the number of data bytes subsequent to the header). After rasterizing and encoding, the bitmap data is decoded and halftoned using a halftone screen before being sent to a print engine. The halftone screen, when applied to the bitmap data, defines the characteristics of the halftone cells used to represent the final output image. A halftone cell is a 2-dimensional matrix of threshold values. When continuous tone data is screened by the halftone cell, each pixel in the continuous tone data corresponds with one of the elements in the halftone cell. To perform the halftone process, each pixel is compared with one or more threshold values in the halftone cell to determine the halftone output value. This process is computationally intensive, and becomes more so as the bit width of an output channel on the print engine increases. Some print engines include color channels that accept multi-bit wide data. In a CMYK print engine for example, the yellow color channel (Y) may accept 2 bit binary data to describe a pel (i.e., a printed dot on a media). When generating halftone data for our example yellow color channel, each continuous tone pixel is compared to three threshold values to generate a binary output of 00, 01, 10, or 11.
One problem with halftoning data within an RL datastream, such as PackBits, is that the data is encapsulated in the RL format. This means that the datastream must be decoded before the threshold values in the halftone cell can be compared to the datastream during the halftone process. Another problem is the large number of threshold comparisons, which may be necessary when generating the halftone output data for a print engine that uses multi-bit output channels. Print engines that utilize multi-bit output channels, in particular, entail the use of multiple threshold values per pixel, which involve significant computational resources to process.